The technical problem posed in the present invention is the problem encountered in the use/adaptation of the network coding in ad hoc network topologies, on multi-flows with a routing modification for existing flows, these flows establishing themselves in a temporally synchronized or non-synchronized manner.
One way of proceeding is to use the “network coding” method. The benefit of network coding, to with relaying a linear combination of received packets instead of relaying the packets separately, is explained in FIGS. 1 and 2.
FIG. 1 presents an example of routing without use of optimization by network coding in the same butterfly topology as that of FIG. 2. In this example it can be seen that the flow X1 transits by means of the transmissions of tagged packets 1, 2, 3, and that the flow X2 transits by means of the transmissions of tagged packets 4, 5, 6. This leads to a total number of 6 transmissions to transmit a packet from the two flows and a heavy use of resources on the nodes C and E which transmit the packets from the 2 flows.
The example given in FIG. 2 makes it possible, by transmitting the combination of a flow X1 and of a flow X2 transmitted respectively by two different sources, to reduce the number of packets to be relayed.
In this example, the source nodes S1 and S2 communicate data to the destination nodes D and F, either directly for the communication from S1 to D and S2 to F, or using the links C and E as relays for the communications from S1 to F and S2 to D. The general principle of network coding consists in linearly combining the stream packets relayed by C and E, in order to reduce the communication data rate on these nodes.
The linear combination proposed in the example in FIG. 2 is achieved by application of the bitwise XOR binary function, leading to Nc(X1, X2), and thus without increasing the size of the packets transmitted, knowing that each of the nodes D and F have already received the data directly, from the flows X1 and X2 respectively. These nodes will therefore be able to extract the information from these flows X1 and X2 respectively. In this figure it will be seen that that there are only four instances of sending 1, 2, 3 and 4. The communication is achieved by broadcast. Sending the same packet to several neighbors has the same data rate cost as sending to a single neighbor.
It will be noted that, in relation to optimal routing without the use of optimization by network coding in this particular topology presented in FIG. 1, the use of network coding on the same topology presented in FIG. 2 leads to a data rate gain of 33%. This leads to an increase in consumption and optimization of resource allocation (nodes C and E).
One of the aims of the method according to the invention is to propose a protocol which makes it possible to determine the best routes for transmissions of data flows in various topological situations in a communications network.
Patent application EP 2 141 865 discloses a method making it possible to combine routing with network coding. When a flow is established, the method consists in counting the number of links shared with other flows by enriching the route request information RREQ with reactive routing. In this document, there is no modification of the route for existing flows, the route being determined flow by flow, without any overall view of all flows.
Before giving some examples which will improve understanding of the invention, a few useful definitions for the description are listed below:                a node (or radio terminal) is one of the basic components of the network. A node has the capability to detect its network neighborhood (i.e. all of the nodes in the network with which it can send and receive information without relay nodes) by means of appropriate signalling known to those skilled in the art. This node provides a radio resource allocation capability making it possible to transmit stream flows to neighbor nodes; a node has the capability to receive data packets from these neighbor nodes, to decode them and store information, to perform algorithmic processing and to transmit packets to its neighbor nodes, with a possibility of selecting a set of its neighbors for data transmission. The connecting links between two nodes are considered bidirectional (the nodes are aware of each other and have allocated some of the resource in such a way as to establish streams and exchange messages in both directions of the connection);        a node is said to be a “source node” if it sends a data flow; as will be described in the rest of the description of the method, this concept of source node can be extended to nodes with a stable link to the source node, and may also be extended to nodes sending a receiver for a flow;        a node is said to be a destination node when it is the destination of one or more flows; as will be described in the rest of the description, this concept of destination node is extended to transit nodes or destination nodes for data flows with a stable link to the destination node or nodes for which it relays the flow. In this case, the real destination node may be the destination of a single flow. The extension of the destination node also applies to nodes sending a receiver for a flow;        the concept of stability is understood in terms of stability of the communication link during the execution of the data flow or flows, an expression known to those skilled in the art;        a transit node or intermediate node is equipped with means for receiving and sending data flows;        a “pivot” node is a transit node identified as having the capability to code the flows it receives by network coding and to send this coded flow;        a preceding node is a node that is situated upstream of the node in question, when travelling along a path leading to an origin node for a stream;        the word stream denotes a data transfer made between two nodes in the network; the stream occurs through transmission of data packets between the nodes;        the stream is established through prior establishment of a route composed of a series of communication nodes. The first element is the source node, other nodes—including the last—are the destination nodes, and the other nodes are relay nodes. Each of the nodes has the capability to communicate directly with the adjacent nodes in the series;        a routing protocol is a protocol which makes it possible to determine a route and to configure each of the nodes in such a way as to relay the stream packets. The setup of such a protocol is not considered a prerequisite for the use of the invention for setting up communication, but may be used in phase 1 of the invention, for which similar traversals are made, notably for the AODV (Ad hoc On-demand Distance Vector) protocol;        the words flow or flux are synonyms for stream here. It is possible to associate a separate identifier Id with each flow (for example from the identifier of the source node that initiates the flow);        an ad hoc network is an expression known to those skilled in the art that denotes a network in which the nodes self-organize and establish communication flow routes, for example by using a routing protocol;        the term “table” signifies a set of elements. These elements may be flow identifiers, numbers indicating a distance from one node to a source node or destination node or else an intermediate node;        an coded flow is generated by a coding function. It is possible, when coding 2 flows, to use the XOR function; the value NN for a flow, relating to a node of the network, is the number of nodes on a path or a route that links the source node for the flow to this node;        each intermediate node updates a flow table which comprises all the active flows that transit through this node. The incoming flow contains an entry for each active flow containing the information (identifier for the flow, preceding hop, next hop, number of flows etc.);        the nodes have the possibility of storing the last two packets received from the flows that transit via these nodes;        the nodes have the possibility of storing a number of messages Mtopo (defined in the rest of the description), for a specifiable time period. This capability is mandatory on the initial stream nodes and optional on the relay nodes;        the nodes have the capability to receive stream establishment requests, linked to a flow, with directives regarding the path on which the flow is to be established, and also regarding the establishment of network coding for some of the nodes on the path. These messages MflowEstab are defined further on in the description;        a data packet header gives a separate identifier to the flow and to the packet of the flow.        